package jun;

import com.sun.deploy.util.ArrayUtil;

import java.nio.charset.Charset;
import java.util.*;

/**
 * @author ：冯涛滔
 * @date ：Created in 2020-6-4 9:14
 * @description：
 * @modified By：
 * @version:
 */
public class Jun04 {
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/queue-reconstruction-by-height/  406. 根据身高重建队列
     * create time: 2020-6-4 9:37
     *
     * @eturn a
     * @params
     */
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0];
            }
        });
        List<int[]> list = new LinkedList<>();
        for (int i = 0; i < people.length; i++) {
            list.add(people[i][1], people[i]);
        }
        return list.toArray(new int[people.length][2]);
    }

    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/advantage-shuffle/  870. 优势洗牌
     * create time: 2020-6-4 9:38
     *
     * @return int[]
     * @params [A, B]
     */
    public static int[] advantageCount(int[] A, int[] B) {
        Arrays.sort(A);
        int[] res = new int[A.length];
        for (int i = 0; i < B.length; i++) {
            int j = 0;
            while (j < A.length && B[i] >= A[j]) {
                j++;
            }
            if (A[j] == -1) {
                j = 0;
                while (A[j] == -1) {
                    j++;
                }
            }
            res[i] = A[j];
            A[j] = -1;
        }
        return res;

    }

    public int[] advantageCount2(int[] A, int[] B) {
        int[] sortedA = A.clone();
        Arrays.sort(sortedA);
        int[] sortedB = B.clone();
        Arrays.sort(sortedB);

        // assigned[b] = list of a that are assigned to beat b
        Map<Integer, Deque<Integer>> assigned = new HashMap();
        for (int b : B) assigned.put(b, new LinkedList());

        // remaining = list of a that are not assigned to any b
        Deque<Integer> remaining = new LinkedList();

        // populate (assigned, remaining) appropriately
        // sortedB[j] is always the smallest unassigned element in B
        int j = 0;
        for (int a : sortedA) {
            if (a > sortedB[j]) {
                assigned.get(sortedB[j++]).add(a);
            } else {
                remaining.add(a);
            }
        }

        // Reconstruct the answer from annotations (assigned, remaining)
        int[] ans = new int[B.length];
        for (int i = 0; i < B.length; ++i) {
            // if there is some a assigned to b...
            if (assigned.get(B[i]).size() > 0)
                ans[i] = assigned.get(B[i]).pop();//因为每一个队列里面只会有有一个元素所以用出栈其实也一样
            else
                ans[i] = remaining.pop();
        }
        return ans;
    }

    public int largestSumAfterKNegations(int[] A, int K) {
        int[] number = new int[201];//-100 <= A[i] <= 100,这个范围的大小是201
        for (int t : A) {
            number[t + 100]++;//将[-100,100]映射到[0,200]上
        }
        int i = 0;
        while (K > 0) {
            while (number[i] == 0)//找到A[]中最小的数字
                i++;
            number[i]--;//此数字个数-1
            number[200 - i]++;//其相反数个数+1
            if (i > 100) {//若原最小数索引>100,则新的最小数索引应为200-i.(索引即number[]数组的下标)
                i = 200 - i;
            }
            K--;
        }
        int sum = 0;
        for (int j = i; j < number.length; j++) {//遍历number[]求和
            sum += (j - 100) * number[j];//j-100是数字大小,number[j]是该数字出现次数.
        }
        return sum;
    }

    public String strWithout3a3b(int A, int B) {
        boolean flag = A > B; //true 就是输出A
        int num = 0;
        int i = 0;
        char[] list = new char[A + B];
        while (A > 0 || B > 0) {
            if (A > B == flag) {
                if (num == 2) {
                    flag = !flag;
                }
            } else {
                flag = A > B;
                num = 0;
            }
            if (flag) {
                list[i] = 'a';
                A--;
            } else {
                list[i] = 'b';
                B--;
            }
            num++;
            i++;
        }
        return String.valueOf(list);
    }
//
//    public String reorganizeString(String S) {
//        char[] chars = S.toCharArray();
//        PriorityQueue<int[]> maxHeap = new PriorityQueue<int[]>(new Comparator<int[]>() {
//            @Override
//            public int compare(int[] o1, int[] o2) {
//                return o2[1 - o1[1]]; //按照字符出现的次数降序排列
//            }
//        });
////        97-122
//        int[] list = new int[26];
//        for (int i = 0; i < chars.length; i++) {
//            list[chars[i] - 97]++;
//        }
//        for (int i = 0; i < list.length; i++) {
//            maxHeap.offer();
//        }
//    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/reorganize-string/submissions/ 767. 重构字符串
     * 建立最大堆 每次选择剩余数量最多并且和上一个字符不重复的输出
     * create time: 2020-6-4 20:37
     * @params [S]
     * @return java.lang.String
     */
    public String reorganizeString2(String S) {

        int[][] chars = new int[26][2];
//储存字母出现的次数以及所对应的下标（用于后续排序后也能找到对应的字母）
        for (int i = 0; i < S.length(); i++) {
            int index = S.charAt(i) - 'a';
            chars[index][0]++;
            chars[index][1] = index;
        }
//排序
        Arrays.sort(chars,new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });
        StringBuilder ans = new StringBuilder();
        while (true) {
//选取第一个最多的字母作为参照 例如a 则有aXaXaXaX
            for (int j = 1; j < chars.length && chars[0][0] > 0; j++) {
                if (chars[j][0] > 0) {
                    ans.append((char) (chars[0][1] + 'a')); //记录
                    chars[0][0]--;
                    ans.append((char) (chars[j][1] + 'a')); //记录
                    chars[j][0]--;
                }
            }
            Arrays.sort(chars, new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o2[0] - o1[0];
                }
            });
// 结束条件 排序完成后如果已经没有字母 或者 只剩下一种字母循环结束
            if (chars[0][0] == 0 || chars[1][0] == 0) {
                break;
            }

        }
//如果剩下的字母数量>1 则必然不可行
// 如果剩下的字母数量==1 则把它添加到末尾
        if (chars[0][0] > 1) return "";
        if (chars[0][0] == 1) ans.append((char) (chars[0][1] + 'a'));
        return ans.toString();

    }
    /**
     * create by: 冯涛滔
     * description: https://leetcode-cn.com/problems/task-scheduler/ 621. 任务调度器
     * 建一个最大堆 每次挑选剩余数量最多的并且没有在休息的出来
     * 休息的就放进休息队列里
     * create time: 2020-6-4 20:39
     * @params [tasks, n]
     * @return int
     */
    public static int leastInterval(char[] tasks, int n) {
        int[][] list = new int[tasks.length][2]; //1任务数量 2第几回合可以进行这个任务
        for (int i = 0; i < tasks.length; i++) { //初始化的时候我们不需要标识
            list[tasks[i]-65][0]++;
            list[tasks[i]-65][1] = 0;
        }
        for (int i = 0; i < list.length; i++) {
            if(list[i][0]==0)
                list[i][1] = Integer.MAX_VALUE;
        }
        int number = 0;
        int i = 0;
        for(;number<tasks.length;i++){
            int k = i;
            Arrays.sort(list, new Comparator<int[]>() { //优先级 看当前回合能不能执行 不能就拉到没有用 可以就按任务量降序
                @Override
                public int compare(int[] o1, int[] o2) {
                    return o1[1]<=k&&o2[1]<=k?o2[0]-o1[0]:o1[1]-o2[1];
                }
            });
            if(list[0][1]<=i){//这个回合可以执行 如果第一个都不能执行其他都一样
                list[0][0]--;
                number++;
                list[0][1] = i+1+n;//设置再次可以执行的时间
                if(list[0][0]==0){//任务全部完成
                    list[0][1] = Integer.MAX_VALUE;
                }
            }
        }
        return i;
    }
    public int leastInterval2(char[] tasks, int n) { //官方题解方法三的优化版
        int[] map = new int[26];
        for (char c : tasks)
            map[c - 'A']++;
        Arrays.sort(map);
        int max_val = map[25] - 1, idle_slots = max_val * n; //idle_slots 最坏的状态就是有那么多回合的空闲 max_val -1 是因为最后一个任务不需要空闲时间就能安排
        for (int i = 24; i >= 0 && map[i] > 0 && idle_slots > 0; i--) {
            if (map[i] == max_val+1) {
//                某个任务和 A 出现的次数相同，例如图 2 中的任务 B。此时我们只能让 B 占据 p - 1 个空闲时间，而在非空闲时间里额外安排一个时间给 B 执行；
                idle_slots -= map[i] - 1;
            } else {
                idle_slots -= map[i];
            }
        }
        return idle_slots > 0 ? idle_slots + tasks.length : tasks.length;//如果还有多的空闲回合就加上
    }


    public static void main(String[] args) {
        int[] list = {12, 24, 8, 32};
        int[] list2 = {13, 25, 32, 11};
        int[] list3 = {8, 5};
        char[] chars= {'A','A','A','A','A','A','B','C','D','E','F','G'};
        leastInterval(chars,2);
        System.out.println(Arrays.toString(advantageCount(list, list2)));
    }
}
